The present invention relates generally to satellite navigation systems. In particular, the invention relates to a method and system for using multiple antennas to obtain position solution for each antenna in a satellite navigation system where signals from fewer than four satellites are available at some antennas.
Global Positioning System or GPS is extensively used for position determination. It is a network of satellites that continuously transmit coded information that are utilized to precisely determine locations on the Earth.
GPS can be divided into three segments viz., a space segment, a control segment and a user segment. The space segment nominally consists of a network of 24 satellites distributed in 6 orbit planes around the Earth. The orbits are so distributed that at any instant of time a receiver positioned anywhere on Earth can receive signals from at least four satellites. The satellites continuously broadcast low power radio signals that travel in the “line of sight”, i.e. the signals cannot travel through opaque objects. GPS signals comprise i) a signal carrier wave, ii) a pseudo random noise code (PRN), and iii) ephemeris and almanac data. The PRN code is unique to each satellite. It is used to calculate the distance between a receiver and the satellites. Ephemeris data contains correction factors that are used by the receiver to interpret GPS signals more accurately. Almanac data contains information about the exact location of the satellites and is necessary to determine the location of the receiver. The control segment comprises 5 control stations. This system controls GPS satellites by tracking them and thereafter providing them with corrected orbital and clock information.
At the user end, a typical receiver receives signals and calculates the distance from a satellite. This is done by measuring the difference between the time of receiving a signal at the user's end and the time of broadcast of the signal from the satellite. The time difference is calculated by measuring the PRN code phase difference between the received signal and an identical signal that was simultaneously generated at the receiver end. For conventional GPS code-phase positioning, a user receiver requires simultaneous measurements of code phase from a minimum of four different satellites to solve for its four unknown space-time coordinates, i.e. three position coordinates and internal clock offset from GPS time. This is a basic form of GPS positioning and provides a navigation solution that is typically accurate to 10 m in a world coordinate frame.
The conventional GPS technique described above suffers from a number of errors from different sources. Apart from receiver clock errors and orbital errors, there are ionosphere and troposphere delays where the satellite signal slows as it passes through the atmosphere. This error is greatly reduced in a method known as Differential GPS (DGPS). DGPS employs a fixed reference station in the above-discussed GPS. This reference station measures its position using GPS. The reference station broadcasts differential correction information over a communication link to all mobile receivers in the vicinity, so that the mobile receivers establish a very accurate position relative to the reference station. The information broadcast by the reference station may be its own raw code phase measurements or a correction factor based on the difference between its current position measurement and a long-term average position. With the use of DGPS, accuracy of around 1-5 meters can be achieved.
The following explanation describes how a conventional GPS (and DGPS) position solution is derived from phase measurements.
Conventional GPS Position Solution
The conventional GPS technique calculates user position and other parameters from pseudorange measurements made by a receiver. This method provides a position solution in a world reference frame with an accuracy of around 10 meters. For differential GPS, the differential code phase measurements represent differences between code phase measurements made simultaneously by a mobile user receiver and a fixed reference station. The differential GPS position solution is in a frame relative to the reference station and the solution is accurate to a few meters.
The pseudorange observation between satellite i and user antenna j is related to the user position and clock bias by the equation:ρij=|rj−xi|+τi  Equation 1
Where ρij is the measured pseudorange, ri is the satellite position, xi is the receiver position, |ri−xi| is the true range, and τi is the receiver clock bias times the speed of light. Various error sources, including antenna line bias etc, that are not essential to the current discussion have been ignored. In differential GPS, ρij is the code-phase difference between the reference antenna and user antenna, and rj is the reference antenna position. To solve for the user position from the pseudorange, Equation 1 may be linearized (as in Equation 2 below) about an apriori estimate of position, {circumflex over (x)}i, where Δxi={circumflex over (x)}i−xi and Δρij is the difference between the predicted measurement, based on {circumflex over (x)}i, and the actual measurement.
                              Δ          ⁢                                          ⁢                      ρ            i                          =                              [                                                                                E                    i                                                                    1                                                      ]                    ⁡                      [                                                                                Δ                    ⁢                                                                                  ⁢                                          x                      i                                                                                                                                        τ                    i                    ′                                                                        ]                                              Equation        ⁢                                  ⁢        2                        Where                                                                Δ          ⁢                                          ⁢                      ρ            i                          ≡                  [                                                                      Δ                  ⁢                                                                          ⁢                                      ρ                                          i                      ⁢                                                                                          ⁢                      1                                                                                                                          ⋮                                                                                      Δ                  ⁢                                                                          ⁢                                      ρ                                          in                      s                                                                                                    ]                                    Equation        ⁢                                  ⁢        3                                          E          i                ≡                  [                                                                      -                                                            e                      ^                                                              i                      ⁢                                                                                          ⁢                      1                                        T                                                                                                      ⋮                                                                                      -                                                            e                      ^                                                              in                      s                                        T                                                                                ]                                    Equation        ⁢                                  ⁢        4                                                      e            ^                                i            ⁢                                                  ⁢            1                          ≡                                            r              j                        -                                          x                ^                            i                                                                                      r                j                            -                                                x                  ^                                i                                                                                    Equation        ⁢                                  ⁢        5            
A set of four or more measurements in equation 2 can be combined into a set of normal equations that can be solved for user position xi. The observation matrix [Ei 1] is usually referred to as the geometry matrix and êij are line-of-sight vectors from antenna i to satellite j. The symbol “1” is shorthand for a column vector of 1's of appropriate dimension.
An application requiring two or more position measurements might simply employ independent GPS receivers for each position measurement, even though there may be constraint relations between the antennas.
In such an instance, each receiver would form its own independent solution based on Equation 2. If the phase information from all such receivers were combined at a central processor, Equation 2 could be extended as Equation 6 and then solved.
                              [                                                                      Δ                  ⁢                                                                          ⁢                                      ρ                    1                                                                                                                        Δ                  ⁢                                                                          ⁢                                      ρ                    2                                                                                                      ⋮                                                                                      Δ                  ⁢                                                                          ⁢                                      ρ                                          n                      a                                                                                                    ]                =                              [                                                                                [                                                                                                                        E                            1                                                                                                    1                                                                                      ]                                                                    0                                                  ⋯                                                  0                                                                              0                                                                      [                                                                                                                        E                            2                                                                                                    1                                                                                      ]                                                                                                                                                            ⋮                                                                              ⋮                                                                                                                                          ⋰                                                  0                                                                              0                                                  ⋯                                                  0                                                                      [                                                                                                                        E                                                          n                              a                                                                                                                                1                                                                                      ]                                                                        ]                    ⁡                      [                                                                                                                                                        Δ                          ⁢                                                                                                          ⁢                                                      x                            1                                                                                                                                                                                        τ                          1                                                                                                                                                                                                                                                              Δ                          ⁢                                                                                                          ⁢                                                      x                            2                                                                                                                                                                                        τ                          2                                                                                                                                                                  ⋮                                                                                                                                                                          Δ                          ⁢                                                                                                          ⁢                                                      x                                                          n                              a                                                                                                                                                                                                                    τ                                                      n                            a                                                                                                                                                                    ]                                              Equation        ⁢                                  ⁢        6            
For applications requiring the highest possible accuracy, a method called carrier-phase differential GPS, or more commonly, real time kinematic (RTK), can be used. In this method, the GPS carrier wave is measured directly and compared to a similar carrier wave (phase) measurement made by the reference station. Using carrier phase differential GPS, accuracies of 1-2 centimeters relative to the reference station can be achieved.
The following explanation describes how GPS carrier phase techniques are used to derive the position solution.
GPS Carrier Phase Techniques
GPS carrier phase techniques employ carrier phase measurements to determine centimeter-level accurate position solutions. A fundamental requirement of all carrier phase techniques is to solve for carrier cycle ambiguities.
At any given sample instant there are more unknowns for which to solve than there are available measurements. Therefore, measurements must (1) be accumulated over multiple sample instances, (2) be taken over the course of some geometric change in the system—by the satellites, user, or both, and (3) contain more than four (at least five) measurements per sample to provide redundancy for obtaining the position solution. Some of the techniques of carrier phase measurement are: 1) Satellite motion [as described in Differential GPS in Global Positioning System: Theory and Applications II, volume 164 of Progress in Aeronautics and Astronautics, pp. 3-50, by Parkinson, B. W. and Spilker, J. J. Jr., Editors. AIAA, 1996.], 2) User motion [as described in “Navigation Integrity for Aircraft Precision Landing Using the Global Positioning System”, Stanford University, pp. 37-66, pp. 150-151, by Pervan, Boris S., Ph.D. Dissertation, 1996.], 3) Integer searching [As described in “Instantaneous Ambiguity Resolution,” KIS Symposium 1990, Banff, Canada, September 1990, by Hatch, R. and in “A New Method of Instantaneous Ambiguity Resolution,” Proceedings of ION GPS-94, Salt Lake City, Utah, Institute of Navigation, Washington, D.C., Sep. 20-24, 1994. by Knight, D.]
In a manner similar to the code phase solution shown above, the relationship between carrier phase measurements and the unknown user position and clock state is provided here as a basis to show how a solution incorporating constraints would differ from conventional carrier phase method. The differential carrier phase measurement between the user and a reference receiver for antenna i and satellite j is related to the position, cycle ambiguity, and clock bias by the following equation:φij=|rj−xi|+τi+Nij  Equation 7
Where φij is the measured differential carrier phase, ri, xi, and τi are as above, and Nij is the cycle ambiguity, in carrier wavelengths. Again, several error sources not essential to the current discussion are ignored here. The various satellite- or user-motion based methods for converting carrier phase information to user state begin with the formulation of a linearized observation matrix relating the differential carrier phase measurements to the unknown position, clock, and cycle ambiguity states. As was done with equation (1) in the code phase solution, equation (7) may be linearized about an a priori estimate of position, {circumflex over (x)}i, where Δxi={circumflex over (x)}i−xi and φij is the difference between the predicted measurement, based on ^xi, and the actual measurement.
                              Δ          ⁢                                          ⁢                      ϕ            i                          =                              [                                                                                E                    i                                                                    1                                                                      I                    _                                                                        ]                    ⁡                      [                                                                                Δ                    ⁢                                                                                  ⁢                                          x                      i                                                                                                                                        τ                    i                    ′                                                                                                                    Δ                    ⁢                                                                                  ⁢                                          N                                              i                        ⁢                                                                                                  ⁢                        2                                                                                                                                          ⋮                                                                                                  Δ                    ⁢                                                                                  ⁢                                          N                                              in                        s                                                                                                                  ]                                              Equation        ⁢                                  ⁢        8                        Where                                                                Δ          ⁢                                          ⁢                      ϕ            i                          ≡                  [                                                                      Δ                  ⁢                                                                          ⁢                                      ϕ                                          i                      ⁢                                                                                          ⁢                      1                                                                                                                          ⋮                                                                                      Δ                  ⁢                                                                          ⁢                                      ϕ                                          in                      s                                                                                                    ]                                    Equation        ⁢                                  ⁢        9                                          I          _                ≡                  [                                                    0                                                                    I                                              ]                                    Equation        ⁢                                  ⁢        10                                          τ          i          ′                ≡                              τ            i                    +                      N                          i              ⁢                                                          ⁢              1                                                          Equation        ⁢                                  ⁢        11                                          Δ          ⁢                                          ⁢                      N            ij                          ≡                              N            ij                    -                      N                          i              ⁢                                                          ⁢              1                                                          Equation        ⁢                                  ⁢        12            
The substitutions of τi′ for τi and integer differences ΔNij for Nij are made because the integers themselves, solved in this manner, are not distinguishable from clock bias, but the integer differences are distinguishable.
Under normal circumstances, the observation matrix [Ei 1 l] does not contain enough information in one measurement update to allow the pseudo-inversion needed to generate the least-squares solution to the system of equations. However, taking many measurements through the course of motion of satellites, the motion of the user, or both, can provide measurement equations that accrue faster in number than the number of new user states, thereby creating a solvable system of equations. In practice, the amount of accumulated data is typically too large to solve in one huge concatenated-matrix inversion, but are instead solved by means of a forward-backward information filter [As described in “Navigation Integrity for Aircraft Precision Landing Using the Global Positioning System”, Stanford University, pp. 37-66, pp. 150-151, 1996 by Pervan, Boris S., Ph.D. Dissertation].
The independent receiver approach can be represented by building a large observation matrix with independent observation matrices for each antenna along the diagonal. The user states for each antenna are likewise stacked into one large vector, as are the corresponding differential phase measurements φij. In this manner, by stacking Equation 8 from each differential phase measurement the following equation is obtained:
                                                                        [                                                                                                    Δ                        ⁢                                                                                                  ⁢                                                  ϕ                          1                                                                                                                                                                        Δ                        ⁢                                                                                                  ⁢                                                  ϕ                          2                                                                                                                                                ⋮                                                                                                                          Δ                        ⁢                                                                                                  ⁢                                                  ϕ                                                      n                            a                                                                                                                                              ]                            =                                                                                                                      ⁢                                                [                                                                                                              [                                                                                                                                                      E                                  1                                                                                                                            1                                                                                                                              I                                  _                                                                                                                                              ]                                                                                            0                                                                    ⋯                                                                    0                                                                                                            0                                                                                              [                                                                                                                                                      E                                  2                                                                                                                            1                                                                                                                              I                                  _                                                                                                                                              ]                                                                                                                                                                                                                  ⋮                                                                                                            ⋮                                                                                                                                                                                                                                                                                                    ⁢                          ⋰                                                                                            0                                                                                                            0                                                                    ⋯                                                                    0                                                                                              [                                                                                                                                                      E                                                                      n                                    a                                                                                                                                                              1                                                                                                                              I                                  _                                                                                                                                              ]                                                                                                      ]                                ⁡                                  [                                                                                                                                                                                                        Δ                                ⁢                                                                                                                                  ⁢                                                                  x                                  1                                                                                                                                                                                                                                        τ                                1                                ′                                                                                                                                                                                                        Δ                                ⁢                                                                                                                                  ⁢                                                                  N                                  12                                                                                                                                                                                                        ⋮                                                                                                                                                                          Δ                                ⁢                                                                                                                                  ⁢                                                                  N                                                                      1                                    ⁢                                                                          n                                      s                                                                                                                                                                                                                                                                                                                                                                                                                                                  Δ                                ⁢                                                                                                                                  ⁢                                                                  x                                  2                                                                                                                                                                                                                                        τ                                2                                ′                                                                                                                                                                                                        Δ                                ⁢                                                                                                                                  ⁢                                                                  N                                  22                                                                                                                                                                                                        ⋮                                                                                                                                                                          Δ                                ⁢                                                                                                                                  ⁢                                                                  N                                                                      2                                    ⁢                                                                          n                                      s                                                                                                                                                                                                                                                                                                                              ⋮                                                                                                                                      Δ                          ⁢                                                                                                          ⁢                                                      x                                                          n                              a                                                                                                                                                                                                                    τ                                                      n                            a                                                    ′                                                                                                                                                              Δ                          ⁢                                                                                                          ⁢                                                      N                                                                                          n                                a                                                            ⁢                              2                                                                                                                                                                                          ⋮                                                                                                                                      Δ                          ⁢                                                                                                          ⁢                                                      N                                                                                          n                                a                                                            ⁢                                                              n                                s                                                                                                                                                                                          ]                                                                                        Equation        ⁢                                  ⁢        13            
However, establishing proper carrier phase measurements requires one of several initialization processes to be performed. The type of process performed depends on the geometric layout of the overall system and motion on the part of either the satellites or the mobile receiver. The initialization process is known as carrier cycle ambiguity resolution or integer resolution. This process typically requires the user to wait for at least a few minutes during which the satellite signal is re-acquired unto its high accuracy mode. The initialization process must be carried out every time a user receiver loses continuous track of a minimum of four satellites.
A frequent limitation in the use of any of the above GPS methods for determining position is the requirement of continuous visibility of four satellites to the GPS antenna. However, the continuous visibility of four satellites is not practical in many real life situations. As the GPS signals travel in the “line of sight”, buildings, terrain, electronic interference, or sometimes even dense foliage can block signal reception, causing limited satellite visibility. For example, when the system is being used to track locations in urban-areas, which are surrounded by skyscrapers visibility to four satellites is hindered. If there are fewer than four satellite signals available, a GPS receiver will lose its positioning ability and will require time to (1) re-acquire a sufficient number of satellite signals and (2) re-initialize to a high accuracy mode.
As a consequence of the line-of-sight visibility requirement, most GPS applications use a tall mast or similar mounting structure to raise the GPS antenna as high as possible. When applied to certain agricultural and construction equipment, large antenna mounting structures may limit the mobility of the implement. Also, large antenna mounts only partially address the problem and often even large antenna mounts are not useful in case of signal blockage.
There are certain GPS based navigation systems that work even with visibility to fewer than four satellites.
One such system is disclosed in “Maintaining GPS Positioning in Steep Turns Using Two Antennae,” Institute of Navigation GPS-95, Palm Springs, Calif., September 1995, by Lawrence, David G., et al. This system uses two antennas, mounted on an airplane, to maintain continuous position tracking even when fewer than four satellites are visible on one of the antennas.
However, this system cannot be generalized to more than two antennas and does not allow for motion and/or clock divergence among a subset of the antennas. This system requires a separate set of four antennas to provide attitude information, which in turn is used to determine the position.
Another such system is disclosed in U.S. Pat. No. 5,977,909, titled “Method And Apparatus For Locating An Object Using Reduced Number Of GPS Satellite Signals Or With Improved Accuracy” and assigned to General Electric Company (Schenectady, N.Y.). This patent discloses a positioning system that involves the use of position constraint to reduce the number of satellite signals required per antenna to determine the position of an object. In this patent, the physical track of a rail car is used to constrain the location of the rail car. Therefore, the number of GPS signals required for determining the position is reduced. This invention can track objects, which follow a specific path, so that a database can be generated. This database is used to provide additional information while determining the position of the object. Unfortunately, the scope of such a system is very limited. This system cannot be used to determine the position in unfamiliar locations, where the path traversed by the object is not known. For example, this invention would not be suitable for positioning farm equipment or automobiles, since the creation of a database in these cases would be almost impossible.
Another system that can determine position using fewer than four GPS satellites is disclosed in U.S. Pat. No. 6,353,412 titled “Method And Apparatus For Determining Position Location Using Reduced Number Of GPS Satellites And Synchronized And Unsynchronized Base Stations”, and assigned to Qualcomm, Incorporated (San Diego, Calif.). This patent discloses a location determining GPS system for wireless receivers. The wireless communication device is adapted to receive these GPS signals and transmit a fourth signal to a base station in response thereto. The base station receives the fourth signal, corrects for the clock bias imposed on the fourth signal by the round trip delay between the base station and the wireless communication device, and uses the unbiased fourth signal to calculate the position of the wireless communication device.
However, this method requires a wireless device so as to communicate with a cellular base station in order to provide satellite almanacs and remove clock-bias. Hence, this system will not work in places where there are no base stations in the vicinity or the base station is not capable of providing the correction factors. This situation could arise in cases when the user is in some isolated or uninhabited locations, and many farms are in fact located in isolated or uninhabited areas.
Another satellite navigation system utilizing fewer than four antennas has been disclosed in U.S. Pat. No. 6,292,132 titled “System And Method For Improved Accuracy In Locating And Maintaining Positions Using GPS”, and assigned to Daimler Chrysler AG (Stuttgart, Del.). This system uses multiple GPS antennas and corresponding processors on a single vehicle in order to maintain position information when fewer than four GPS satellites are visible. This system calculates differential path lengths between the received position information signals and at least two antenna-processor pairs to determine the cone angles between them. The corresponding position information of the mobile vehicle is maintained using the initial position information and the determined cone angles. However, this system requires prior knowledge of the initial position. Moreover, this system is not very accurate as it is based on extrapolating the position based on the initial position and the information generated by the sensors attached to the steering wheel.
Another method for obtaining location solutions even in the absence of four GPS signals is disclosed in U.S. Pat. No. 5,935,194 titled “Method For Using External Constraints To Improve The Speed And Reliability Of Phase Ambiguity Resolution In Real-Time Kinematic Initialization”, and assigned to Trimble Navigation Limited (Sunnyvale, Calif.). This invention uses externally provided constraints, such as altitude to reduce the computational burden in determining the position. This invention works particularly in the case when there are a limited number of satellites visible to the receiver.
However, this system utilizes various constraints only to simplify the computational burden and in resolving integer cycle ambiguities. It does not use constraints to specifically circumvent the need for the fourth satellite, nor does it use the constraints to improve or enable centimeter-level positioning once the cycle ambiguities have been resolved. This system simply focuses on using constraints to better traverse the search tree involved in resolving the integer ambiguity cycle. Furthermore, this system only relates to search-type methods for resolving integer cycle ambiguities and, therefore, it relies on dual frequency measurements to reduce the search space to a manageable size (and as such does not benefit motion-based methods).
U.S. Pat. No. 5,548,293, titled “System And Method For Generating Attitude Determinations Using GPS” and assigned to Cohen describes a system for determining the attitude of a four-antenna configuration on a vehicle. The system uses physical constraints and motion-based methods for determining integer cycle ambiguities. The system also can measure wing flexure if the vehicle is an airplane and two of the four antennas are mounted on the wings. However, this system only describes configurations with four or more antennas and four or more satellites. It relates only to attitude determination of a single body. It does not provide a method for vehicles with multiple bodies connected by a linkage, such as a vehicle and an implement.
Therefore, there is a need for a system that can provide position and location information in a satellite navigation system, even when there are less than four satellite signals. In particular, there is a need for an invention that can provide the position of vehicles, which have multiple bodies connected by linkages, such as earth moving machines (that are working in remote or uninhabited areas and that do not have any constraints with respect to their initial or transient locations), even when antennas on some of the linkages cannot receive satellite signals. Further, there is a need for a method that obviates the need for cumbersome antenna mounting structures to receive signals from GPS satellites.